package com.salim.leetcode.$90;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class SubsetsII {
    //1 2 3 2 分解成 1*（2  *（3 * 2））即每个元素都有要和不要两种选择
    //如果当前元素的包括在已经存在列表里 则不走不要的选择以去重
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        return loop(nums,0);
    }

    public List<List<Integer>> loop(int[] nums,int index){
        List<List<Integer>> result = new ArrayList<>();
        int base = nums[index];
        if(nums.length-1==index){
            result.add(Collections.singletonList(base));
            result.add(Collections.emptyList());
        }else{
            List<List<Integer>> subResult = loop(nums,index+1);
            for(List<Integer> sub:subResult){
                List<Integer> newSub1 = new ArrayList<>(sub);
                //不包括base的情况
                if(!newSub1.contains(base)){
                    result.add(newSub1);
                }
                //包括base的情况
                List<Integer> newSub2 = new ArrayList<>(sub);
                newSub2.add(base);
                result.add(newSub2);
            }
        }
        return result;
    }
}
